MacTech 1 to 12/MacTech-vol-1-12.toast/Source/MacTech® Magazine/Volume 12 - 1996/12.08 Aug 96/12.08 Prog Chal/PostPlus.cpp

C/C++ Source or Header | 1996-06-09 | 22.6 KB | 933 lines | [TEXT/R*ch]

/*
  31 May 1996.
  Submission to MacTech Programmer's challenge for May-96.
  Copyright 1996, Ernst Munter, Kanata, ON, Canada.

        "Postman's Sort"

Problem Statement
-----------------
  Sort an address file, using distribution sort, and avoid
  any direct or disguised (indirect) comparison between
  sort keys of the input records.

Solution
--------
  It was tempting to create a sorted index tree of the keys,
  and then sort input records by comparing (descending) the
  sort tree.

  However, I think that would not have been in the spirit
  of the Challenge, which was, I believe, to find a fast
  implementation of Bob Ramey's postman's sort algorithm.

  Hence, this solution works entirely by distributing
  records into bins, or stacks, directly indexed by a single
  character.

  Tabs, and end-of-record markers are converted to \x0,
  the range \x1 to \x1F is used to sort numeric fields by
  their length.

  Characters above 'a' are reduced by 0x20, which makes all
  upper and lower case characters the same.  Coincidentally,
  it also sets {|}~ equal to [\]^.

  Whether the input file fits in memory or not, the principle
  of sorting is the same:

  All records are parsed into nodes and attached to stacks
  based on the current sort key, for example the first letter
  of country.

  Then each stack is recursively sorted on the next sort key,
  i.e. the second letter of country, in the same manner.

  If this is done in-memory (MemSort) the stacks are linked
  and detached from the global STACK array, before sorting
  each stack.

  If the stack was too large to fit in memory, it is sent
  in segments to a temporary file on disk.
  The temp file then contains interleaved segments of stacks
  which we keep track of in a local variable (bin).

  To continue sorting, the segments of a particular stack
  are retrieved from disk, and the whole stack may now
  fit in memory for final sorting.  If it does not, it
  is again sorted into segments and sent to a new temp file
  on disk.

  The number of temp files needed is equal to the recursion
  depth of the disk sort, until a stack can be sorted to the
  finish in memory.  The more memory we have, the fewer temp
  files are needed.

Assumptions
-----------

  tmpfile() is used to create temporary files.  Depending
  on system setup, the system may run out of files to open,
  and sorting will then stop.

  The order of numerical fields will be natural numerical,
  that is 9, 12, 30, 100.  However, leading zero's are not
  expected (or we get 41, 80, 053, 102).

  The length of a purely numeric field to be handled correctly
  should not exceed 31. Longer numeric fields could get sorted
  behind fields starting with punctuation.

  The longest record expected should be substantially less
  than the constant MINMEM which is set to 1024, but this
  limit can be relaxed.  It plays a role only when we are
  very short of memory.

  All ASCII characters may occur, and will be sorted on.
  Any control characters other than Tab (0x09) will be treated
  as end-of-record indicators.

  The sort is not "stable", in the sense that the order of
  equivalent records (differing in case only, as an example)
  is not preserved.  Records are tossed on stacks and into
  bins, and are frequently retrieved in reverse order.
  Furthermore, running the program with different amounts
  of storage may result in a different order as well (U/L case).
*/

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <string.h>


#undef shortCut
//#define shortCut

#define uchar unsigned char
#define ushort unsigned short
#define ulong unsigned long

#define NUM_KEYS     224
#define MINMEM         1024
#define MIN_BUFFER     512
#define DEF_BUFFER_SIZE 16384
#define numFields     9
#define lastField     (numFields-1)
#define TAB_CHAR     0x09
#define END_RECORD     0x0D

typedef struct Node Node;
struct     Node {
  uchar*    ref;
  Node*     next;
  Node*     link;
  ushort    fld[numFields];
  ushort    len;
};

typedef struct tHeader tHeader;
struct     tHeader {
  long     next;
  int     size;
  int     key;
};

typedef struct Bin Bin;
struct     Bin {
  FILE* tf;        //temp file
  long    next;        //next segment in temp file
  int    bytesLeft;    //in current segment
  long  fpos[NUM_KEYS];
};

typedef struct OutputBuffer OutputBuffer;
struct     OutputBuffer {
  int    space;        //space left
  int    size;        //size of buffer
  uchar c[4];        //will be c[size]
};

/************ 908 bytes of static variables ***************/

static     FILE*         theOutFile;
static     OutputBuffer*     buffer;
static     int         topKey;
static     Node*         STACK[NUM_KEYS];

/**************** macros and prototypes********************/

// Output buffer functions:
// The output buffer accumulates characters to be sent to
// the output file.  The block size is chosen as 16K,
// but reduced to 8K if less than 128K of storage is
// available.
// The buffer isreleased if, after many recursions storage
// space is severely reduced and we need the memory
// for sorting.

void     FlushBuffer();
int     OpenBuffer(uchar* storage,int storageSize);
void     CloseBuffer();
void     BufferedWrite(uchar* text,int size);
void     BufferedSend(Node* node);

// in-memory sort and parsing functions:

Node*     Link(int* numeric);
int     TestNumeric(int key,uchar* text,int len);
void     Dist(Node* node,int field,int offset,int test);
void     MemSort(int field,int offset);
int     Parse(uchar* text,Node* node,int size,int field,int offset,int test);


// SStream functions:
// SStreams are virtual files which are interleaved on a single disk file.
// Each SStream may consist of several segments, linked together
// through small headers (tHeader) on the disk.  The last segment
// is pointed to from a "bin".
// Bins administer access to these streams.

void     InitBin(Bin* bin);
int     OpenBin(Bin* bin);
void     ResetBin(Bin* bin);
void     CloseBin(Bin* bin);
int     SendToTemp(Bin* bin);
int     SegmentSize(Node* node);
void     Send(Node* node,FILE* f);
int     SStreamSeek(Bin* bin,int key,long pos);
int     SStreamRead(uchar* text0,int size,Bin* bin);
long     SStreamSize(Bin* bin,int key);
void     SendSStreamOut(uchar* text,int storageSize,Bin* bin,int key);

// The DiskSort function is called from PostmansSort, and calls
// itself recursively. With each recursion, the calling Bin structure
// must be preserved which reduces the storage available for the
// called DiskSort function.  This wastage is somewhat controlled
// by recovering the unused part of the Bin structure, since
// keys in the high ASCII ranges would frequently not be needed.

// Bins could also have been put on the procedure stack, but this
// could put a more severe limit on recursion depth. (about 1K
// per Bin), depending on the environment.

int     RecoverMemory();
int     DiskSort(
  Bin*     inBin,
  uchar* storage,
  int   storageSize,
  int     field,
  int     offset);


/**************************   *********************************/

#ifdef     __BORLANDC__
#define OSErr int
#else
    pascal
#endif
OSErr     PostmansSort(
  FILE     *inFile,          /* stream containing sort input */
  FILE     *outFile,         /* stream to contain sort output */
  void     *privateStorage,  /* preallocated storage for your use */
  size_t storageSize      /* number of bytes of privateStorage */
);

#define QUIT(rc) {CloseBin(bin); return rc;}
#define EMPTY_BIN(bin,key) (bin->fpos[key]<0)


#ifdef shortCut
#define maxField 32

// The shortCut functions are used to detect the case of a single
// key in a stack of records.  This means we can jump directly to
// the end of the field.

// SingleKey() detects this by AND and OR of all remaining
// characters in a field, across all records.  If the results
// of the AND and the OR are identical, then all records have
// the same characters in the rest of the field.


int SingleKey(uchar* hi,uchar* lo,int field,int offset,int reset);
void MoveSingleStack();
void MoveSingleBin(Bin* bin);

#endif
/**********************************************************/


// the following #ifdef takes care of some
// compiler incompatibilities

#ifdef     __BORLANDC__
#define OSErr int
#else
    pascal
#endif
OSErr PostmansSort(
  FILE *inFile,          /* stream containing sort input */
  FILE *outFile,         /* stream to contain sort output */
  void *privateStorage,  /* preallocated storage for your use */
  size_t storageSize     /* number of bytes of privateStorage */
) {
uchar*     storage=(uchar*)privateStorage;
Bin*     bin=(Bin*)storage;
uchar*  text;
Node*     node;

long     fileSize;
long     shortage;
long    curPos;
int     textSize;
int     recovered;
int    rc;
int     nextField=lastField;

#ifdef shortCut
int    skipField=0;
uchar     hi[maxField];
uchar     lo[maxField];
#endif

// Setup storage:

  text=(uchar*)(bin+1);
  theOutFile=outFile;
  storageSize-=OpenBuffer(storage,storageSize);
  storageSize-=sizeof(Bin);
  storageSize-=sizeof(Node);
  if (storageSize<MINMEM) return 10;

// Determine size of input file and read as much as possible

  curPos=ftell(inFile);
  fseek(inFile,0,2);
  fileSize=ftell(inFile);
  fseek(inFile,curPos,0);
  textSize=fread(text,1,storageSize,inFile);

// Parse input data.  Nodes grow from the top of storage
// down into the text, and may cause some of it to be reloaded

  node=(Node*)(text+storageSize);
  topKey=0;
  shortage=Parse(text,node,textSize,nextField,0,1);
  curPos=textSize-shortage;

  if (fileSize-curPos==0) {    //everything fit

    MemSort(nextField,0);

  } else {            //distribute into bins

#ifdef shortCut
  if (nextField) {
    skipField=SingleKey(hi,lo,nextField,0,1);
  }
#endif

    InitBin(bin);
    do {
      if (0!=(rc=SendToTemp(bin))) QUIT(rc);
      fseek(inFile,curPos,0);
      textSize=fread(text,1,storageSize,inFile);
      node=(Node*)(text+storageSize)-1;
      shortage=Parse(text,node,textSize,nextField,0,1);
      curPos+=textSize-shortage;

#ifdef shortCut
        if (skipField) {
          skipField=SingleKey(hi,lo,nextField,0,0);
        }
#endif

    } while(curPos<fileSize);
    if (0!=(SendToTemp(bin))) QUIT(rc);

#ifdef shortCut
      if (skipField) {
        MoveSingleBin(bin);
        recovered=RecoverMemory();
        if (0!=(rc=DiskSort(
          bin,
      text-recovered,
      storageSize+recovered,nextField,skipField))) QUIT(rc);
      } else
#endif
      {
        recovered=RecoverMemory();
        if (0!=(rc=DiskSort(
          bin,
      text-recovered,
      storageSize+recovered,nextField,0))) QUIT(rc);
      }

    CloseBin(bin);

  }

  FlushBuffer();
  return 0;
}

void InitBin(Bin* bin) {
  memset(bin->fpos,-1,sizeof(bin->fpos));
  bin->next=0;
  bin->bytesLeft=0;
  bin->tf=0;
}

int OpenBin(Bin* bin) {
  if (bin->tf==0) {
    if (0==(bin->tf=tmpfile()))
      return 5;    // unable to open temp file
  }
  return 0;
}

void ResetBin(Bin* bin) {
  memset(bin->fpos,-1,sizeof(bin->fpos));
  bin->next=0;
  bin->bytesLeft=0;
  if (bin->tf) fseek(bin->tf,0,0);
}

void CloseBin(Bin* bin) {
  if (bin->tf) {
    fclose(bin->tf);
  }
}

int Parse(
    uchar* text,
    Node* node,
    int size,
    int field,
    int offset,
    int test) {

// returns the shortage, i.e. the difference between the
// end of the loaded text and the end of the last record parsed.
// The shortage is caused by the fact that we load text up to
// the storage limit, but then overwrite some of it by the
// parsed nodes which grow downwards from the top.  In this
// way we don't have to guess at the size of a typical record.

uchar*     record=text;
int     xfield=0;
uchar*     textEnd=text+size;
  while (text<(uchar*)node) {
    int c=*text++;
    if (c<' ') {
      if (c==TAB_CHAR) {

// mark off those fields
    xfield++;
    if (xfield>lastField) return 4;
    node->fld[xfield]=(ushort)(text-record);
      } else {

// any other CTL-char is treated as END_RECORD:
    int key=*(record+node->fld[field]+offset);

// fill in fields of node and hook to STACK:
    node->ref=record;
    node->link=0;
    node->fld[0]=0;
    node->len=(ushort)(text-record);

// key is the character in the current key position
// modified to
//    0 if end of field,
//     lower case becomes upper case
//    length of field if numeric field detected

    if (node->len==1) key=0;
    else if (key>='a') key-=0x20;
    else if (key<' ') key=0;
    else if (test)
      key=TestNumeric(key,node->ref+node->fld[field],
          node->fld[field+1]-node->fld[field]-1);

// keep track of the highest key value used, for future economies.

    node->next=STACK[key];
    if (key>topKey) topKey=key;
    STACK[key]=node--;
    record=text;
    xfield=0;
      }
    }
    if (text>=textEnd)
      return 0;        //no shortage
  }

  return textEnd-record;
}

static mms;

void MemSort(int field,int offset) {
int endField=(int)STACK[0],numeric=0;
Node* node;
    mms++;
  node=Link(&numeric);
  while (node) {
    Node* nextNode=node->link;
    if (0==node->next) {     //no need to sort a single record
      BufferedSend(node);
      endField=0;
    } else if (endField) {    //go to next field
      int nextField=field-1;
      endField=0;
      if ((field==7)&&(offset>0)) nextField-=2;
      Dist(node,nextField,0,1);
      MemSort(nextField,0);
    } else if (numeric) {     //test same key position for value
      numeric--;
      Dist(node,field,offset,0);
      MemSort(field,offset);
    } else {            //test next key position
      Dist(node,field,offset+1,0);
      MemSort(field,offset+1);
    }
    node=nextNode;
  }
}

Node* Link(int* numeric) {
// detaches stacks under the same key from STACK[] and
// links their first nodes together
Node* node=0;
Node* n;
int key;
  for (key=topKey;key>=0;key--) {
    if (0 != (n=STACK[key])) {
      if ((key<' ') && (key>0)) (*numeric)++;
      n->link=node;
      node=n;
      STACK[key]=0;
    }
  }
  topKey=0;
  return node;
}

void Dist(Node* node,int field,int offset,int test) {
// scan all nodes in a stack and redistribute them
// back on STACK[] depending on the next key value.
  do {
    Node*  nextNode;
    int    key=*(node->ref+node->fld[field]+offset);
    if (key>='a') key-=0x20;
    else if (key<' ') {
      key=0;
      if (field==0) {    //sorting done for this node
        nextNode=node->next;
        node->next=0;
    BufferedSend(node);
    node=nextNode;
    continue;
      }
    } else if (test) {
      key=TestNumeric(key,node->ref+node->fld[field],
          node->fld[field+1]-node->fld[field]-1);
    }
    nextNode=node->next;
    if (key>topKey) topKey=key;
    node->next=STACK[key];
    STACK[key]=node;
    node=nextNode;
  } while (node);
}

int TestNumeric(int key,uchar* text,int len) {
// returns the field length of a numeric field,
// otherwise returns key unchanged
int i;
  for (i=0;i<len;i++) {
    int c=*text;
    if (c>'9') return key;
    if (c<'0') return key;
    text++;
  }
  return len;
}

int DiskSort(
  Bin* inBin,
  uchar* storage,
  int storageSize,
  int field,
  int offset) {

// recursively callable version of PostmansSort()

Bin*     bin=(Bin*)storage;
uchar*     text;
Node*     node;

long     fileSize;
int     textSize;
long     shortage;
long    curPos;

int     key;
int    rc;
int    recovered;
int    topKeyIn=topKey;


#ifdef shortCut
int    skipField;
uchar     hi[maxField];
uchar     lo[maxField];
#endif

  InitBin(bin);
  storageSize-=sizeof(Bin);
  storageSize-=sizeof(Node);
  if (storageSize<MINMEM) {
    if (buffer) {
      storageSize+=buffer->size+sizeof(OutputBuffer)-4;
      CloseBuffer();
      if (storageSize<MINMEM) return 8;
    } else return 9;
  }
  text=(uchar*)(bin+1);
  for (key=0;key<=topKeyIn;key++) {
    int nextField,nextOffset,numericTest;
    if (EMPTY_BIN(inBin,key)) continue;
    if (0==(fileSize=SStreamSize(inBin,key))) continue;

    nextField=field;
    nextOffset=offset;

#ifdef shortCut
    skipField=0;
#endif

    topKey=0;
    if (key==0) {        //end of field reached

      if ((nextField==7)&&(nextOffset>0)) nextField=4;

      else if (nextField==0) {  //copy whole stream
    SendSStreamOut(text,storageSize,bin,0);
    continue;

      } else nextField--;

      nextOffset=0;
      numericTest=1;
    } else if (key<' ') {    //start of a numeric field
      nextOffset=0;
      numericTest=0;
    } else {                    //a typical field
      nextOffset++;
      numericTest=0;
    }

    SStreamSeek(inBin,key,0);
    textSize=SStreamRead(text,storageSize,inBin);
    node=(Node*)(text+storageSize);

    shortage=Parse(text,node,textSize,nextField,nextOffset,numericTest);
    curPos=textSize-shortage;

    if (fileSize-curPos==0) {    //sort in memory

      MemSort(nextField,nextOffset);

    } else {            //sort in temp files

#ifdef shortCut
    if ((nextField!=7) || (nextOffset==0)) {
      skipField=SingleKey(hi,lo,nextField,nextOffset,1);
    }
#endif

      do {
    if (0!=(rc=SendToTemp(bin))) QUIT(rc);
    SStreamSeek(inBin,key,curPos);
    textSize=SStreamRead(text,storageSize,inBin);
    node=(Node*)(text+storageSize)-1;
    shortage=Parse(text,node,textSize,nextField,nextOffset,numericTest);
    curPos+=textSize-shortage;

#ifdef shortCut
        if (skipField) {
          skipField=SingleKey(hi,lo,nextField,nextOffset,0);
        }
#endif

      } while(curPos<fileSize);
      if (0!=(rc=SendToTemp(bin))) QUIT(rc);

#ifdef shortCut
      if (skipField) {
        MoveSingleBin(bin);
    recovered=RecoverMemory();
        if (0!=(rc=DiskSort(
          bin,
      text-recovered,
      storageSize+recovered,nextField,skipField))) QUIT(rc);
      } else
#endif
      {
        recovered=RecoverMemory();
        if (0!=(rc=DiskSort(
          bin,
      text-recovered,
      storageSize+recovered,nextField,nextOffset))) QUIT(rc);
      }

      ResetBin(bin);
    }
  }
  CloseBin(bin);
  return 0;
}

static sst;

int SendToTemp(Bin* bin) {
// send each segment (stack of equal key records) to disk,
// bin->fpos[key] points to the start of the last segment
// stored. The segment header points to the previous
// segment or -1 if this is the first.

int key,rc;
Node* node;
  if (0!=(rc=OpenBin(bin))) return rc;
  for (key=0;key<NUM_KEYS;key++) {
    if (0 != (node=STACK[key])) {
      tHeader th;
      long pos;
      STACK[key]=0;
      th.size=SegmentSize(node);
      th.next=bin->fpos[key];
      th.key=key+('#'<<8);
      pos=ftell(bin->tf);
      fwrite(&th,1,sizeof(tHeader),bin->tf);
      sst++;
      bin->fpos[key]=pos;
      Send(node,bin->tf);
    }
  }
  return 0;
}

int SegmentSize(Node* node) {
// The length of a segment needs to be known for the header,
// before we store the text records.  This functions scans
// through all nodes of a stack and adds up their lengths.
int s=0;
  do {
    s+=node->len;
    node=node->next;
  } while(node);
  return s;
}

void Send(Node* node,FILE* f) {
// Sends a stack to disk, either the temp file, or
// the output file in the case of unbuffered output.
  do {
    fwrite(node->ref,1,node->len,f);
    node=node->next;
  } while(node);
}

int SStreamSeek(Bin* bin,int key,long pos) {
// returns error=7 if no SStream, or if seeked beyond size
long fpos=bin->fpos[key];
tHeader th;
  if (0==bin->tf) return 6;
  while (fpos>=0) {
    fseek(bin->tf,fpos,0);
    fread(&th,1,sizeof(th),bin->tf);
    if (pos<th.size) {
      fseek(bin->tf,pos,1);
      bin->bytesLeft=th.size-pos;
      bin->next=th.next;
      return 0;
    } else {
      pos-=th.size;
      fpos=th.next;
    }
  }
  return 7;
}

int SStreamRead(uchar* text0,int size,Bin* bin) {
// reads from current position reached with SStreamSeek()
// returns the actual number of bytes read
long fpos;
tHeader th;
int bytes2read;
uchar* text=text0;
  if (bin->bytesLeft) {
    if (bin->bytesLeft>size) bytes2read=size;
    else bytes2read=bin->bytesLeft;
    fread(text,1,bytes2read,bin->tf);
    text+=bytes2read;//even if fread comes short
    size-=bytes2read;
  }
  fpos=bin->next;
  while ((size) && (fpos>=0)) {
    fseek(bin->tf,fpos,0);
    fread(&th,1,sizeof(th),bin->tf);
    if (th.size>size) bytes2read=size;
    else bytes2read=th.size;
    fread(text,1,bytes2read,bin->tf);
    text+=bytes2read;//even if fread comes short
    size-=bytes2read;
    fpos=th.next;
  }
  return text-text0;
}

long SStreamSize(Bin* bin,int key) {
// determines the total SStream size by adding up the
// sizes of all its segments.
long fpos=bin->fpos[key];
tHeader th;
long size=0;
  while (fpos>=0) {
    fseek(bin->tf,fpos,0);
    fread(&th,1,sizeof(th),bin->tf);
    size+=th.size;
    fpos=th.next;
  }
  return size;
}

void SendSStreamOut(uchar* text,int storageSize,Bin* bin,int key) {
// function to copy an entire SStream to the output file, which
// can happen when there is a large number of identical records.
long fpos=bin->fpos[key];
tHeader th;
  while (fpos>=0) {
    fseek(bin->tf,fpos,0);
    fread(&th,1,sizeof(th),bin->tf);
    while(th.size){
      int textSize=storageSize;
      if (textSize>th.size) textSize=th.size;
      fread(text,1,textSize,bin->tf);
      BufferedWrite(text,textSize);
      th.size-=textSize;
    }
    fpos=th.next;
  }
}

#ifdef shortCut

int SingleKey(uchar* hi,uchar* lo,int field,int offset,int reset) {
int key;
Node* node;
int endField;
int i;
  for (key=0;key<topKey;key++) {
    if (STACK[key]) return 0;
  }
  node=STACK[topKey];
  endField=node->fld[field+1]-node->fld[field]-offset-1;
  if (endField==0) return 0;
  if (endField>=maxField) return 0;

  if (reset) for (i=0;i<=endField;i++) {hi[i]=0;lo[i]=0xFF;}

  while (node) {
    uchar* f=node->ref+node->fld[field]+offset;
    for (i=0;i<=endField;i++) {
      uchar c=*f++;
      lo[i] &= c;
      hi[i] |= c;
      if (hi[i] != lo[i]) return 0;
    }
    node=node->next;
  }
  if (hi[endField] >= ' ') return 0;
  return endField;
}

void MoveSingleStack() {
  STACK[0]=STACK[topKey];
  STACK[topKey]=0;
  topKey=0;
}

void MoveSingleBin(Bin* bin) {
  bin->fpos[0]=bin->fpos[topKey];
  bin->fpos[topKey]=-1;
  topKey=0;
}

#endif

int RecoverMemory() {
// unused top part of the current bin
  return (NUM_KEYS-topKey-1)*sizeof(long);
}

void FlushBuffer() {
int bytes2send=buffer->size-buffer->space;
  if (bytes2send) {
    fwrite(buffer->c,1,bytes2send,theOutFile);
  }
  buffer->space=buffer->size;
}

int OpenBuffer(uchar* storage,int storageSize) {
// allocates 1/8 of available memory, up to a maximum of
// DEF_BUFFER_SIZE as output buffer for outFile

int maxSize=storageSize>>3;
int bufferSize=DEF_BUFFER_SIZE;
  while (bufferSize>maxSize) bufferSize>>=1;
  if (bufferSize>=MIN_BUFFER) {
    buffer=(OutputBuffer*)(storage+storageSize-
      (bufferSize+sizeof(OutputBuffer)-4));
    buffer->size=bufferSize;
    buffer->space=bufferSize;
    return bufferSize+sizeof(OutputBuffer)-4;
  } else return 0;
}

void CloseBuffer() {
  FlushBuffer();
  buffer=0;
}

void BufferedWrite(uchar* text,int size) {
  if (buffer) {
    if (size > buffer->space) {
      int n1=buffer->space;
      int n2=size-buffer->space;
      memcpy(buffer->c+buffer->size-buffer->space,text,n1);
      buffer->space=0;
      FlushBuffer();
      BufferedWrite(text+n1,n2);
    } else {
      memcpy(buffer->c+buffer->size-buffer->space,text,size);
      buffer->space-=size;
    }
  } else {
    fwrite(text,1,size,theOutFile);
  }
}

void BufferedSend(Node* node) {
  if (buffer) {
    do {
      BufferedWrite(node->ref,node->len);
      node=node->next;
    } while(node);
  } else Send(node,theOutFile);
}